#include <iostream>
using namespace std;

long long a,b,x,y,t;
void extgcd(long long a, long long b){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	extgcd(b, a%b);
	t=x;
	x=y;
	y=t-a/b*y;
}

int main(){
	cin>>a>>b;
	extgcd(a,b);
	cout<<(x+b)%b<<endl;
	return 0;
}